InforLorV4, Main, Exploration, bibRecord, 001112

SyMT: finding symmetries in SMT formulas

Identifieur interne : 001112 ( Main/Exploration ); précédent : 001111; suivant : 001113

SyMT: finding symmetries in SMT formulas

Auteurs : Carlos Areces [Argentine] ; David Déharbe [Brésil] ; Pascal Fontaine [France] ; Orbe Ezequiel [Argentine]

Source :

RBID : Hal:hal-00867816

Abstract

The QF UF category of the SMT-LIB test set contains many formulas with symmetries, and breaking these symmetries results in an important speedup [8]. This paper presents SyMT, a tool to nd and report symmetries in SMT formulas. SyMT is based on the reduction of the problem of detecting symmetries in formulas to nding automorphisms in a graph representation of these formulas. The output of SyMT may be used to improve SMT formulas to enforce the SMT solver to examine only one assignment out of many symmetric ones. We show that the classic propositional symmetry breaking technique can be lifted to SMT and yields a generic technique to break the symmetries found by SyMT. Experiments on a large part of the SMT-LIB show that symmetries are pervasive in most categories.

Url:

https://hal.inria.fr/hal-00867816

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000031
to stream Hal, to step Curation: 000031
to stream Hal, to step Checkpoint: 001025
to stream Main, to step Merge: 001123
to stream Main, to step Curation: 001112

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="da">SyMT: finding symmetries in SMT formulas</title>
<author><name sortKey="Areces, Carlos" sort="Areces, Carlos" uniqKey="Areces C" first="Carlos" last="Areces">Carlos Areces</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-41526" status="VALID"><orgName>Facultad de Matemática, Astronomía y Física [Cordoba]</orgName>
<orgName type="acronym">FaMAF</orgName>
<desc><address><addrLine>Facultad de Matemática, Astronomía y Física Universidad Nacional de Córdoba Medina Allende y Haya de la Torre Ciudad Universitaria 5000, Córdoba Capital, Córdoba, Argentina</addrLine>
<country key="AR"></country>
</address>
<ref type="url">http://www.famaf.unc.edu.ar/</ref>
</desc>
<listRelation><relation active="#struct-367029" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-367029" type="direct"><org type="institution" xml:id="struct-367029" status="INCOMING"><orgName>Universidad Nacional de Córdoba</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Argentine</country>
</affiliation>
</author>
<author><name sortKey="Deharbe, David" sort="Deharbe, David" uniqKey="Deharbe D" first="David" last="Déharbe">David Déharbe</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-110670" status="VALID"><orgName>Universidade Federal do Rio Grande do Norte [Natal]</orgName>
<orgName type="acronym">UFRN</orgName>
<desc><address><addrLine>Caixa Postal 1524 - Campus Universitário Lagoa Nova, CEP 59078-970 | Natal/RN</addrLine>
<country key="BR"></country>
</address>
<ref type="url">https://www.sistemas.ufrn.br/portal/PT/</ref>
</desc>
</hal:affiliation>
<country>Brésil</country>
</affiliation>
</author>
<author><name sortKey="Fontaine, Pascal" sort="Fontaine, Pascal" uniqKey="Fontaine P" first="Pascal" last="Fontaine">Pascal Fontaine</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-107895" status="VALID"><idno type="RNSR">201020692C</idno>
<orgName>Modeling and Verification of Distributed Algorithms and Systems</orgName>
<orgName type="acronym">VERIDIS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/veridis</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423084" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName>
<orgName type="acronym">LORIA - FM</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Ezequiel, Orbe" sort="Ezequiel, Orbe" uniqKey="Ezequiel O" first="Orbe" last="Ezequiel">Orbe Ezequiel</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-41526" status="VALID"><orgName>Facultad de Matemática, Astronomía y Física [Cordoba]</orgName>
<orgName type="acronym">FaMAF</orgName>
<desc><address><addrLine>Facultad de Matemática, Astronomía y Física Universidad Nacional de Córdoba Medina Allende y Haya de la Torre Ciudad Universitaria 5000, Córdoba Capital, Córdoba, Argentina</addrLine>
<country key="AR"></country>
</address>
<ref type="url">http://www.famaf.unc.edu.ar/</ref>
</desc>
<listRelation><relation active="#struct-367029" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-367029" type="direct"><org type="institution" xml:id="struct-367029" status="INCOMING"><orgName>Universidad Nacional de Córdoba</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Argentine</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00867816</idno>
<idno type="halId">hal-00867816</idno>
<idno type="halUri">https://hal.inria.fr/hal-00867816</idno>
<idno type="url">https://hal.inria.fr/hal-00867816</idno>
<date when="2013-07-08">2013-07-08</date>
<idno type="wicri:Area/Hal/Corpus">000031</idno>
<idno type="wicri:Area/Hal/Curation">000031</idno>
<idno type="wicri:Area/Hal/Checkpoint">001025</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001025</idno>
<idno type="wicri:Area/Main/Merge">001123</idno>
<idno type="wicri:Area/Main/Curation">001112</idno>
<idno type="wicri:Area/Main/Exploration">001112</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="da">SyMT: finding symmetries in SMT formulas</title>
<author><name sortKey="Areces, Carlos" sort="Areces, Carlos" uniqKey="Areces C" first="Carlos" last="Areces">Carlos Areces</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-41526" status="VALID"><orgName>Facultad de Matemática, Astronomía y Física [Cordoba]</orgName>
<orgName type="acronym">FaMAF</orgName>
<desc><address><addrLine>Facultad de Matemática, Astronomía y Física Universidad Nacional de Córdoba Medina Allende y Haya de la Torre Ciudad Universitaria 5000, Córdoba Capital, Córdoba, Argentina</addrLine>
<country key="AR"></country>
</address>
<ref type="url">http://www.famaf.unc.edu.ar/</ref>
</desc>
<listRelation><relation active="#struct-367029" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-367029" type="direct"><org type="institution" xml:id="struct-367029" status="INCOMING"><orgName>Universidad Nacional de Córdoba</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Argentine</country>
</affiliation>
</author>
<author><name sortKey="Deharbe, David" sort="Deharbe, David" uniqKey="Deharbe D" first="David" last="Déharbe">David Déharbe</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-110670" status="VALID"><orgName>Universidade Federal do Rio Grande do Norte [Natal]</orgName>
<orgName type="acronym">UFRN</orgName>
<desc><address><addrLine>Caixa Postal 1524 - Campus Universitário Lagoa Nova, CEP 59078-970 | Natal/RN</addrLine>
<country key="BR"></country>
</address>
<ref type="url">https://www.sistemas.ufrn.br/portal/PT/</ref>
</desc>
</hal:affiliation>
<country>Brésil</country>
</affiliation>
</author>
<author><name sortKey="Fontaine, Pascal" sort="Fontaine, Pascal" uniqKey="Fontaine P" first="Pascal" last="Fontaine">Pascal Fontaine</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-107895" status="VALID"><idno type="RNSR">201020692C</idno>
<orgName>Modeling and Verification of Distributed Algorithms and Systems</orgName>
<orgName type="acronym">VERIDIS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/veridis</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423084" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName>
<orgName type="acronym">LORIA - FM</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Ezequiel, Orbe" sort="Ezequiel, Orbe" uniqKey="Ezequiel O" first="Orbe" last="Ezequiel">Orbe Ezequiel</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-41526" status="VALID"><orgName>Facultad de Matemática, Astronomía y Física [Cordoba]</orgName>
<orgName type="acronym">FaMAF</orgName>
<desc><address><addrLine>Facultad de Matemática, Astronomía y Física Universidad Nacional de Córdoba Medina Allende y Haya de la Torre Ciudad Universitaria 5000, Córdoba Capital, Córdoba, Argentina</addrLine>
<country key="AR"></country>
</address>
<ref type="url">http://www.famaf.unc.edu.ar/</ref>
</desc>
<listRelation><relation active="#struct-367029" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-367029" type="direct"><org type="institution" xml:id="struct-367029" status="INCOMING"><orgName>Universidad Nacional de Córdoba</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Argentine</country>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The QF UF category of the SMT-LIB test set contains many formulas with symmetries, and breaking these symmetries results in an important speedup [8]. This paper presents SyMT, a tool to nd and report symmetries in SMT formulas. SyMT is based on the reduction of the problem of detecting symmetries in formulas to nding automorphisms in a graph representation of these formulas. The output of SyMT may be used to improve SMT formulas to enforce the SMT solver to examine only one assignment out of many symmetric ones. We show that the classic propositional symmetry breaking technique can be lifted to SMT and yields a generic technique to break the symmetries found by SyMT. Experiments on a large part of the SMT-LIB show that symmetries are pervasive in most categories.</div>
</front>
</TEI>
<affiliations><list><country><li>Argentine</li>
<li>Brésil</li>
<li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Metz</li>
<li>Nancy</li>
</settlement>
<orgName><li>Université de Lorraine</li>
</orgName>
</list>
<tree><country name="Argentine"><noRegion><name sortKey="Areces, Carlos" sort="Areces, Carlos" uniqKey="Areces C" first="Carlos" last="Areces">Carlos Areces</name>
</noRegion>
<name sortKey="Ezequiel, Orbe" sort="Ezequiel, Orbe" uniqKey="Ezequiel O" first="Orbe" last="Ezequiel">Orbe Ezequiel</name>
</country>
<country name="Brésil"><noRegion><name sortKey="Deharbe, David" sort="Deharbe, David" uniqKey="Deharbe D" first="David" last="Déharbe">David Déharbe</name>
</noRegion>
</country>
<country name="France"><region name="Grand Est"><name sortKey="Fontaine, Pascal" sort="Fontaine, Pascal" uniqKey="Fontaine P" first="Pascal" last="Fontaine">Pascal Fontaine</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001112 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001112 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:hal-00867816
   |texte=   SyMT: finding symmetries in SMT formulas
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

SyMT: finding symmetries in SMT formulas

SyMT: finding symmetries in SMT formulas

Source :

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri